#ifndef STX_ALGORITHM_ROTATE_HPP
#define STX_ALGORITHM_ROTATE_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/swap.hpp>

namespace stx {

template <class ForwardIterator>
ForwardIterator
rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
{
    if (first == middle)
        return last;
    if (middle == last)
        return first;
    ForwardIterator i = middle;
    while (1) {
        stx::swap(*first, *i);
        ++first;
        if (++i == last) {
            break;
        }
        if (first == middle) {
            middle = i;
        }
    }
    ForwardIterator r = first;
    if (first != middle) {
        i = middle;
        while (1) {
            stx::swap(*first, *i);
            ++first;
            if (++i == last) {
                if (first == middle) {
                    break;
                }
                i = middle;
            } else if (first == middle) {
                middle = i;
            }
        }
    }
    return r;
}

} // namespace stx

#endif // STX_ALGORITHM_ROTATE_HPP
